package developer.算法.回溯.分隔回文串;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangyongkang
 * @time 2025/4/2 10:16
 * @description 代码
 * 131. 分割回文串
 * <p>
 * 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串(回文 串是向前和向后读都相同的字符串) 。返回 s 所有可能的分割方案。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 * <p>
 * 输入：s = "a"
 * 输出：[["a"]]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 16
 */
public class FenGeHuiWenChuan {

    public static void main(String[] args) {
//        SolutionOfficial solution = new SolutionOfficial();
//        List<List<String>> aab = solution.partition("aab");
        Solution4 solution = new Solution4();
        List<List<String>> aab = solution.partition("aab");
        for (List<String> strings : aab) {
            System.out.println();
            strings.forEach(a -> System.out.print(a + " "));
        }
    }

    static class Solution4 {
        List<List<String>> result;

        public List<List<String>> partition(String s) {
            result = new ArrayList<>();
            dfs(new ArrayList<>(), s, 0);
            return result;
        }

        private void dfs(List<String> current, String s, int start) {
            if (start == s.length()) {
                result.add(new ArrayList<>(current));
                return;
            }

            for (int i = start; i < s.length(); i++) {
                String tmp = s.substring(start, i + 1);
                if (isHuiWen(tmp)) {
                    current.add(tmp);
                    dfs(current, s, i + 1);
                    current.remove(current.size() - 1);
                }


            }
        }

        private boolean isHuiWen(String str) {
            int length = str.length();
            Queue<Character> stack = new LinkedList<>();
            int mid = length / 2;
            for (int i = 0; i < mid; i++) {
                stack.offer(str.charAt(i));
            }
            int start = length - 1;
            while (!stack.isEmpty()) {
                Character poll = stack.poll();
                char c = str.charAt(start--);
                if (!poll.equals(c)) {
                    return false;
                }
            }
            return true;
        }

    }


    static class Solution3 {
        private List<List<String>> res;

        public List<List<String>> partition(String s) {
            res = new ArrayList<>();
            dfs(new ArrayList<>(), 0, s);
            return res;
        }

        private void dfs(List<String> current, int start, String str) {
            if (start == str.length()) {
                res.add(new ArrayList<>(current));
                return;
            }
            for (int i = start; i < str.length(); i++) {
                String s = str.substring(start, i + 1);
                if (isHuiWen(s)) {
                    current.add(s);
                    dfs(current, i + 1, str);
                    current.remove(current.size() - 1);
                }
            }
        }

        private boolean isHuiWen(String str) {
            int length = str.length();
            Queue<Character> stack = new LinkedList<>();
            int mid = length / 2;
            for (int i = 0; i < mid; i++) {
                stack.offer(str.charAt(i));
            }
            int start = length - 1;
            while (!stack.isEmpty()) {
                Character poll = stack.poll();
                char c = str.charAt(start--);
                if (!poll.equals(c)) {
                    return false;
                }
            }
            return true;
        }
    }


    static class Solution {
        int length;
        List<String> current;
        List<List<String>> result;
        int[][] cache;

        public List<List<String>> partition(String s) {
            length = s.length();
            current = new ArrayList<>();
            result = new ArrayList<>();
            cache = new int[length + 1][length + 1];
            dfs(0, s);
            return result;
        }

        private void dfs(int start, String word) {
            if (start == length) {
                result.add(new ArrayList<>(current));
                return;
            }

            for (int i = start; i < length; i++) {
                if (isHuiWen(start, i + 1, word)) {
                    String huiwen = word.substring(start, i + 1);
                    current.add(huiwen);
                    dfs(i + 1, word);
                    current.remove(current.size() - 1);
                }
            }
        }

        private boolean isHuiWen(int start, int end, String word) {
            int i = cache[start][end];
            if (i == 0) {
                cache[start][end] = handleHuiWen(start, end, word) ? 1 : 2;
            }
            return cache[start][end] == 1;
        }

        private boolean handleHuiWen(int start, int end, String word) {
            String substring = word.substring(start, end);
            boolean isTrue = true;
            int left = 0, right = substring.length() - 1;
            while (left <= right) {
                char l = substring.charAt(left);
                char r = substring.charAt(right);
                isTrue = isTrue && l == r;
                left++;
                right--;
            }
            return isTrue;
        }

    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/palindrome-partitioning/solutions/639633/fen-ge-hui-wen-chuan-by-leetcode-solutio-6jkv/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    static class SolutionOfficial {
        int[][] f;
        List<List<String>> ret = new ArrayList<List<String>>();
        List<String> ans = new ArrayList<String>();
        int n;

        public List<List<String>> partition(String s) {
            n = s.length();
            f = new int[n][n];

            dfs(s, 0);
            return ret;
        }

        public void dfs(String s, int i) {
            if (i == n) {
                ret.add(new ArrayList<String>(ans));
                return;
            }
            for (int j = i; j < n; ++j) {
                if (isPalindrome(s, i, j) == 1) {
                    ans.add(s.substring(i, j + 1));
                    dfs(s, j + 1);
                    ans.remove(ans.size() - 1);
                }
            }
        }

        // 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
        public int isPalindrome(String s, int i, int j) {
            if (f[i][j] != 0) {
                return f[i][j];
            }
            if (i >= j) {
                f[i][j] = 1;
            } else if (s.charAt(i) == s.charAt(j)) {
                f[i][j] = isPalindrome(s, i + 1, j - 1);
            } else {
                f[i][j] = -1;
            }
            return f[i][j];
        }
    }

}
